package org.chengn.level_hard.context2454;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Stack;

/**
 * @Title: Context2454
 * @Author ChengN
 * @Package org.chengn.level_hard.context2454
 * @Date 2023/12/13 0:15
 * @description: 下一个更大元素IV
 */
public class Context2454 {
    public int[] secondGreaterElement(int[] nums) {
        Stack<Point> stack1 = new Stack();
        PriorityQueue<Point> queue = new PriorityQueue<>(Comparator.comparingInt((Point p) -> p.x));

        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; ++i) {
            while (!queue.isEmpty() && queue.peek().x < nums[i]) {
                Point point = queue.poll();
                res[point.y] = nums[i];
            }
            while (!stack1.empty() && stack1.peek().x < nums[i]) {
                queue.add(stack1.pop());
            }
            stack1.push(new Point(nums[i], i));
        }

        while (!stack1.empty()) {
            res[stack1.pop().y] = -1;
        }
        while (!queue.isEmpty()) {
            res[queue.poll().y] = -1;
        }
        return res;
    }



    static class Point {
        public int x;
        public int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}
